//堆排序
#include<stdio.h>

//交换
void Swap(int* left, int* right) {
	int temp = *left;
	*left = *right;
	*right = temp;
	return;
}

//向下调整
void AdjustDown(int* arr, int size, int parent) {
	int child = (2 * parent) + 1;
	while (child < size) {
		if (child + 1 < size && arr[child] > arr[child + 1])
			child += 1;
		if (arr[child] < arr[parent]) {
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = (2 * parent) + 1;
		}
		else
			return;
	}
	return;
}

//排降序,建小堆
void HeapSort(int* arr, int size) {
	//建堆
	for (int i = (size - 2) / 2; i >= 0; i--) {
		AdjustDown(arr, size, i);
	}
	//堆排序
	int end = size - 1;
	while (end) {
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, end, 0);
		end--;
	}
	return;
}

//打印
void HeapPrint(int arr[], int size) {
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return;
}
int main() {
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	int numSize = sizeof(arr) / sizeof(arr[0]);
	printf("排序前>>");
	HeapPrint(arr, numSize);
	HeapSort(arr, numSize);
	printf("排序后>>");
	HeapPrint(arr, numSize);
	return 0;
}